package leetcode_600;

import java.util.List;

/**
 *@author 周杨
 *LongestWordInDictionaryThroughDeleting_524 给定一个串s和一个字典 判断字典里最长的一个串能够是s的子串
 *describe:遍历即可 AC 19%
 *2018年9月10日 下午12:28:51
 */
public class LongestWordInDictionaryThroughDeleting_524 {
	public String findLongestWord(String s, List<String> d) {
        String res="";
        for(String str:d) {
        	if(isSubsequence(str, s))
        		res=judge(res, str);
        }
        return res;
    }
	
	public boolean isSubsequence(String a, String b){
        int i=0, j=0;
        while(i<a.length() && j<b.length()) if (a.charAt(i)==b.charAt(j++)) i++;
        return i==a.length();
	}
	
	public String judge(String a,String b) {
		if(a.length()>b.length())
			return a;
		else if(a.length()<b.length())
			return b;
		for(int i=0;i<a.length();++i) {
			char ca=a.charAt(i);
			char cb=b.charAt(i);
			if(ca!=cb) {
				return ca<cb?a:b;
			}
		}
		return a;
	}
}
